package org.example.day02;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO
 * 有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。现有两组字母，分别表示后序遍历（左孩子-&gt;右孩子-&gt;父节点）和中序遍历（左孩子-&gt;父节点-&gt;右孩子）的结果，请输出层次遍历的结果。
 *
 * 有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。
 * 现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请输出层次遍历的结果。
 * @date 2024/3/11 15:22
*/
public class test025 {
    // 根据后序遍历和中序遍历的结果重建二叉树
    // 定义二叉树节点类
    static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode(char val) {
            this.val = val;
        }
    }

    // 根据后序遍历和中序遍历结果构建二叉树
    public static TreeNode buildTree(char[] inorder, char[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }
        // 使用中序遍历结果构建节点值与位置的映射
        Map<Character, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        // 递归构建二叉树
        return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, inorderMap);
    }

    // 递归构建二叉树的辅助方法
    private static TreeNode buildTreeHelper(char[] inorder, int inStart, int inEnd, char[] postorder,
                                            int postStart, int postEnd, Map<Character, Integer> inorderMap) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        // 后序遍历的最后一个节点是根节点
        char rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        // 获取根节点在中序遍历中的位置
        int rootIndex = inorderMap.get(rootVal);
        // 构建左子树
        root.left = buildTreeHelper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + rootIndex - inStart - 1, inorderMap);
        // 构建右子树
        root.right = buildTreeHelper(inorder, rootIndex + 1, inEnd, postorder, postStart + rootIndex - inStart, postEnd - 1, inorderMap);
        return root;
    }

    // 层次遍历二叉树
    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    public static void main(String[] args) {
        // 测试数据
        char[] inorder = {'D', 'B', 'E', 'A', 'F', 'C'};
        char[] postorder = {'D', 'E', 'B', 'F', 'C', 'A'};

        // 构建二叉树
        TreeNode root = buildTree(inorder, postorder);

        // 输出层次遍历结果
        System.out.print("层次遍历结果: ");
        levelOrderTraversal(root);
        // 输出预期结果: A B C D E F
    }
}
